Skip to main content

Patterns

1. Two Pointers​

[[Two Pointer]]

Description: This method uses two pointers to traverse an array or a list from different ends or directions.

  • Two Pointers is a pattern where two pointers iterate through the data structure in tandem until one or both of the pointers hit a certain condition
  • Two Pointers is often useful when searching pairs in a sorted array or linked list
  • Two Pointers are needed because with just pointer, you would have to continually loop back through the array to find the answer, this back and forth with a single iterator is inefficient for time and space complexity

Usage: Particularly useful for ordered data structures, where we can make intelligent decisions based on the position of the pointers.

  • Some ways to identify that the given problem might require a two pointer
    • It will feature problems where you deal with sorted array (or Linked List) and need to find a set of elements that fufill certain conditions
    • The set of elements in the array is a pair, triple, or subarray
  • Common problems you use the sliding two pointers with
    • Squaring a sorted array
    • Triples that sum to zero
    • Comparing strings that contains backspaces

Example Problems:

  • Pair with Target Sum
  • Remove Duplicates
  • Squaring a Sorted Array

2. Island (Matrix Traversal)​

Description: Involves traversing a matrix to find 'islands' or contiguous groups of elements.

Usage: Generally used in grid-based problems, especially when we need to group connected elements together.

Example Problems:

  • Number of Islands
  • Max Area of Island
  • Flood Fill

3. Fast & Slow Pointers​

Description: In this method, two pointers move at different speeds in a data structure.

  • Also known as the Hare & Tortoise algorithm, is a pointer algorithm that uses two pointers which move through the array (or sequence/linked list) at different speeds. This approach is quite useful when dealing with cyclic linked or arrays
  • By moving at different speeds, the algorithm proves that the two pointers are bound to meet. The fast pointer should catch the slow pointer once both the pointers are in a cyclic loop.

Usage: Commonly used to detect cycles in a structure, find middle elements, or to solve other specific problems related to linked lists.

  • Some ways to identify that the given problem might require a Fast and Slow pattern
    • The problem will deal with a loop in a linked list or array
    • When you need to know the position of a certain element or the overall length of the linked list
  • When should I use it over the [[1. Overview#1. Two Pointers | Two Pointers pattern]]:
    • There are some cases where you shouldn't use the Two Pointer approach such as in a singly linked list where you can't move in a backwards direction. An example of when to use the Fast and Slow pattern is when you're trying to determine if a linked list is a palindrome

Example Problems:

  • LinkedList Cycle
  • Middle of the LinkedList
  • Palindrome LinkedList

More information: [[Linked List#Linked List Two Pointer]]

4. Sliding Window​

[[Sliding Window]] Description: This pattern involves creating a 'window' into the data structure and then moving that window around to gather specific information.

  • Used to perform a required operation on a specific window size of a given array or linked list, such as finding the longest subarray containing all 1s
  • In some cases, the window size remains constant and in other cases the size grows or shrinks

Usage: Mostly used in array or list-based problems where you need to find a contiguous subset that fulfills certain conditions.

  • Some ways to identify that the given problem might require a sliding window
    • The problem input is a linear data structures such as linked list, array, or string
    • You're asked to find the longest/shortest substring, subarray or a desired value

Example Problems:

  • Maximum Sum Subarray of Size K
  • Smallest Subarray with a given sum
  • Longest Substring with K Distinct Characters

5. Merge Intervals​

Description: This pattern involves merging overlapping intervals.

Usage: Often used in problems involving time intervals, ranges, or sequences.

Example Problems:

  • Merge Intervals
  • Insert Interval
  • Intervals Intersection

6. Cyclic Sort​

Description: This pattern involves sorting an array containing numbers in a given range.

Usage: Useful in situations where the data involves a finite range of natural numbers.

Example Problems:

  • Cyclic Sort
  • Find the Missing Number
  • Find all Duplicates

7. In-place Reversal of a Linked List​

Description: This pattern involves reversing elements of a linked list in-place.

Usage: Generally used when reversing a sequence without using extra space.

Example Problems:

  • Reverse a LinkedList
  • Reverse a Sub-list
  • Reverse Every K-element Sub-list

[[Tree]] Description: This pattern involves level-by-level traversal of a tree.

  • This pattern is based on the Breadth First Search (BFS) technique to traverse a tree and uses a queue to keep track of all the nodes of a level before jumping onto the next level.
  • Any problem involving the traversal of a tree in a level-by-level order can be efficiently solved using this approach
  • The Tree BFS pattern works by pushing the root node to the queue and then continually iterating until the queue is empty. For each iteration, we remove the node at the head of the queue and "visit" that node. After removing each node from the queue, we also insert all of its children into the queue.

Usage: Used when we need to traverse a tree or graph in a level-by-level (breadth-first) manner.

  • Some ways to identify that the given problem might require a Tree BFS pattern
    • If you' asked to traverse a tree in a level-by-level fashion (or level order traversal)

Example Problems:

  • Level Order Traversal
  • Reverse Level Order Traversal
  • Zigzag Traversal

[[Tree]] Description: This pattern involves traversing a tree or graph depth-wise before visiting siblings or neighbors.

  • Tree DFS is based on the Depth First Search (DFS) technique to traverse a tree.
  • You can use recursion (or a stack for the iterative approach) to keep track of all the previous (parent) nodes while traversing
  • The Tree DFS pattern works by starting at the root of the tree, if the node is not a leaf you need to do three things:
    • Decide whether to process the current node now (pre-order), or between processing two children (in-order) or after processing both children (post-order)
    • Make two recursive calls for both the children of the current node to process them

Usage: Used when you need to search deeper into a tree/graph first before going across.

  • Some ways to identify that the given problem might require a Tree DFS pattern
    • If you're asked to traverse a tree with in-order, preorder, or postorder DFS
    • If the problem requires searching for something where the node is closer to a leaf

Example Problems:

  • Binary Tree Path Sum
  • All Paths for a Sum
  • Count Paths for a Sum

10. Two Heaps​

[[Heap#Two Heaps Pattern]] Description: This pattern involves using two heaps to divide a set of numbers into two parts.

  • In many problems, we are given a set of elements such that we can divide them into two parts. To solve the problem we are interested in knowing the smallest element in one part and the biggest element in the other part. This pattern is an efficient approach to solve such problem.

Usage: Useful when you need to find median numbers in a sequence, or other similar problems.

  • Ways to identify the Two Heaps pattern:
    • Useful in situations like Priority Queue, Scheduling
    • If the problem states that you need to find the smallest/largest/median elements of a set
    • Sometimes, useful in problems featuring a binary tree data structures

Example Problems:

  • Find the Median of a Number Stream
  • Sliding Window Median
  • Maximize Capital

11. Subsets​

Description: This pattern involves generating all subsets of a set.

  • A huge number of coding interview problems involve dealing with Permutation and Combination of a given set of elements. The pattern usually uses [[Backtracking]] to solve these kind of problems.

Usage: Helpful for solving problems that require exploring all subsets of a given set.

Example Problems:

  • Subsets
  • Subsets With Duplicates
  • Permutations

[[Binary Search]] Description: This is a tweaked version of the binary search algorithm.

  • Whenever you are given a sorted array, linked list, or matrix, and are asked to find a certain element, the best algorithm you can use is Binary Search

Usage: Used when a simple binary search isn't sufficient, like finding a number in a bitonic array.

Example Problems:

  • Order-agnostic Binary Search
  • Ceiling of a Number
  • Next Letter

13. Top 'K' Elements​

[[Heap]] Description: This pattern is used to find the top 'k' elements among a certain category.

  • Any problem that asks us to find the top/smallest/frequent "K" elements among a given set falls under this pattern

  • The best data structure to keep track of "K" elements is Heap. This pattern will make use of the Heap to solve multiple problems dealing with "K" elements at a time from a set of given elements.

  • The pattern looks like this

    • We would need a way to continuously keep track of a (or many) smallest/largest element => Use a heap
    • Insert "K" elements into the min-heap or max-heap based on the problem
    • Iterate through the remaining numbers and if you find one that is larger than what you have in the heap, then remove that number and insert the larger one or decide what to do with the largest/smallest element (pop, replace, etc)

Usage: Commonly used in problems involving sorting, searching, and in heap data structures.

  • Some ways to identify the Top K element
    • If you're asked to find the top/smallest/frequent K elements of a given set
    • If you're asked to sort an array to find an exact element

Example Problems:

  • Top K Frequent Numbers
  • Kth Largest Number in a Stream
  • Top K Frequent Elements

14. Bitwise XOR​

Description: This pattern involves the use of Bitwise XOR to solve various array-based problems.

Usage: Used when we need to manipulate and compare bits directly.

Example Problems:

  • Single Number
  • Two Single Numbers
  • Complement of Base 10 Number

15. Backtracking​

[[Backtracking]] Description: This pattern involves exploring all possible solutions and then backtracking to correct the course whenever you're on the wrong path.

Usage: Typically used for solving complex combinatorial problems, puzzles, and games.

Example Problems:

  • Sudoku Solver
  • N-Queens
  • Generate Parentheses

16. 0/1 Knapsack (Dynamic Programming)​

[[DP]] [[Knapsack]] Description: This pattern deals with problems where items have different values and weights, and we need to determine the maximum value we can carry.

Usage: Typically used in optimization problems, especially those involving physical constraints.

Example Problems:

  • 0/1 Knapsack
  • Equal Subset Sum Partition
  • Subset Sum

17. Topological Sort (Graph)​

[[Graph#Topological Sort | Topological Sort]] Description: This pattern involves sorting nodes in a directed graph in a specific order where the preceding node comes before the following node.

  • Topological Sort is used to find a linear ordering of elements that have dependencies on each other (event B is dependent on event A, A comes before B in topological ordering)

Usage: Used for scheduling problems and in scenarios where order needs to be imposed on how you process nodes.

  • Some ways to identify that the given problem might require a Topological Sort pattern
    • The problem will deal with graphs that have no directed cycles
    • If you're asked to update all objects in a sorted order
    • If you have a class of objects that follow a particular order

Example Problems:

  • Task Scheduling Order
  • All Tasks Scheduling Orders
  • Alien Dictionary

18. K-way Merge​

Description: This pattern involves merging 'k' sorted lists.

Usage: Typically used in problems involving lists, where merging is required.

Example Problems:

  • Merge K Sorted Lists
  • Kth Smallest Number in M Sorted Lists
  • Smallest Number Range

19. Monotonic Stack​

[[Stack#Monotonic Stack | Monotonic Stack]] Description: This pattern involves using a stack to maintain a monotonic (either entirely non-increasing or non-decreasing) order of elements.

Usage: Often used for solving problems where you need to find the next greater or smaller elements.

Example Problems:

  • Next Greater Element
  • Next Smaller Element
  • Largest Rectangle in Histogram

20. Multi-threaded​

Description: This pattern involves designing algorithms that can execute multiple threads in parallel.

Usage: Used in situations where a task can be divided into independent sub-tasks that can execute concurrently.

Example Problems:

  • Invert Binary Tree
  • Binary Search Tree Iterator
  • Same Tree

21. Union Find​

[[Union Find]] Description: Union Find, also known as Disjoint Set Union (DSU), is a data structure that keeps track of a partition of a set into disjoint subsets.

Usage: Particularly useful for problems where we need to find whether 2 elements belong to the same group or need to solve connectivity-related problems in a graph or tree.

Example Problems:

  • Graph Redundant Connection
  • Number of Provinces
  • Is Graph Bipartite

Algorithms

These are helpful algorithms that usually comes up in interview, these list may share some overlaps to the [[1. Overview#Patterns | Patterns section]] but some maybe to niche to be called a patterns, that's why I split it out to this section.

Binary Search [[Binary Search]]

Merge Sort and Quick Sort

  • Understanding sorting algorithms for custom sorting problems

Two-Pointer Technique [[Two Pointer]]

  • Used for sorted arrays, finding pairs or triplets that meet a condition
  • Example problems:

Sliding Window [[Sliding Window]]

Activity Selection

Huffman Encoding

  • Useful for compression-related problems

Kruskal's and Prim's Algorithm

Knapsack Variants [[DP]] and [[Knapsack]]

Longest Common Subsequence (LCS) [[DP#DP on String]]

Matrix-based Dynamic Programming

Breadth-First Search (BFS) [[Graph]] and [[Tree]]

Depth-First Search (DFS) [[Graph#DFS]] and [[Tree]]

  • For traversals, connected components, backtracking

Dijkstra's Algorithm [[Graph#Dijkstra's Shortest Path]]

Union-Find (Disjoint Set Union) [[Union Find]]

Topological Sorting [[Graph#Topological Sort]]

Binary Tree Traversals [[Tree]]

Lowest Common Ancestor (LCA) [[Tree#Lowest Common Ancestor]]

Trie (Prefix Tree)

KMP Algorithm

Manacher's Algorithm

Greatest Common Divisor (GCD)

Sieve of Eratosthenes

Backtracking - Permutations and Combinations [[Backtracking]]

Heap / Priority Queue [[Heap]]

Bit Manipulation

  • Basic operations (AND, OR, XOR, shifts)
  • Subset generation using binary representation
  • Single number problems using XOR
  • Bitmask DP for state handling

Monotonic Stack [[Stack#Monotonic Stack]]

Prefix Sum and Difference Arrays [[Prefix Sum]] and [[Special Techniques#Difference Array]]

Miscellaneous Techniques

Resources